package xyz.scootaloo.alg.tool

/**
 * 使用位运算模拟boolean数组
 *
 * @author flutterdash@qq.com
 * @since 2021/4/16 23:00
 */
class IntSet {
    /**
     * [cache] int数组, 每个int可以模拟32个数字
     * [limit] 存储数字的区间的上限
     * [offset] 存储数字的区间的下限 offset=0, limit=20; 即[0, 20)
     * [cap] 数组的容量
     */
    private val cache: IntArray
    private val limit: Int
    private val offset: Int
    private val cap: Int

    constructor() : this(0, 4096)

    constructor(bound: Int) : this(0, bound)

    constructor(form: Int, to: Int) {
        if (form >= to)
            throw RuntimeException("边界错误")
        val interval = to - form
        val capacity = if (interval % 32 == 0)
            (interval.shr(5))
        else
            (interval.shr(5)) + 1
        this.cache = IntArray(capacity)
        this.offset = form
        this.limit = to
        this.cap = capacity
    }

    fun put(number: Int) {
        checkBorder(number)
        val realNumber = number - offset
        val index = realNumber.shr(5)
        val shiftBits = realNumber % 32
        cache[index] = cache[index].or(base.shl(shiftBits))
    }

    fun contains(number: Int): Boolean {
        checkBorder(number)
        val realNumber = number - offset
        val index = realNumber.shr(5)
        val shiftBits = realNumber % 32
        return cache[index].and(base.shl(shiftBits)) != 0
    }

    fun remove(number: Int) {
        if (!contains(number))
            return
        val realNumber = number - offset
        val index = realNumber.shr(5)
        val shiftBits = realNumber % 32
        cache[index] = cache[index].xor(base.shl(shiftBits))
    }

    fun clear() {
        for (idx in 0 until cap) {
            cache[idx] = 0
        }
    }

    private fun checkBorder(number: Int) {
        if (number < offset || number >= limit)
            throw java.lang.RuntimeException("存储的数值超出范围")
    }

    override fun toString(): String {
        return "IntSet(limit=$limit, offset=$offset, cap=$cap)"
    }

    companion object {
        @JvmStatic
        val base = 1
    }

}
